dojo.provide("mydojo.ComputerScience.BinarySearchTree");
dojo.declare("mydojo.ComputerScience.BinarySearchTree",null,{
	constructor: function(){
		this._root = null;
	},
	add:function(value){
		var current;
		var node = {
			value: value,
			left:null,
			right:null
		}
		if(this._root === null){
			this._root = node;
		}else{
			current = this._root;
			while(true){
				if(value < current.value){
					if(current.left === null){
						current.left = node;
						break;
					}else{
						current = current.left;
					}
				}else if(value > current.value){
					if(current.right === null){
						current.right = node;
						break;
					}else{
						current = current.right;
					}
				}else{
					break;
				}
			}
			
		}
	},
	contains: function(value){
		var found = false;
		var current = this._root;
		while(!found && current){
			if(value < current.value){
				current = current.left;
			}else if(value > current.value){
				current = current.right;
			}else{
				found = true;
			}
		}
		return found;
	},
	traverse: function(process){
		var inOrder = function(node){
			if(node){
				if(node.left){
					inOrder(left);
				}
				process.call(this,node);
				if(node.right){
					inOrder(node.right);
				}
			}
		};
		inOrder(this._root);
	},
	remove: function(value){
		//写了很多了，终于想明白了如果要删除一个节点其中他有两个字节点的时候的原理
		//因为我们知道一个节点左边所有的子孙节点必定小于本节点。一个节点的有边节点
		//必定大于本节点。所以当我们要删除这个节点的时候，必须找一个替身，来保证
		//上面的两点要求。所以现在的需要就转换为找到一个替换节点，把它替换掉就行了。
		//其中有两个节点可以满足。1.就是这个待删除节点的左subtree的最大节点（也就是最右边节点）。
		//这样就能保证左边的所有的子节点都小于这个节点。而左边的都大于。同理。
		//2.就是找到右边subtree的最小节点（也就是最左边节点）。进行替换。
		var found = false;
		var current = this._root;
		var parent = null;
		var childCount;
		var replacement, replacementParent;
		
		while(!found && current){
			if(value < current.value){
				parent = current;
				current = current.left;
			}else if(value > current.value){
				parent = current;
				current = current.right;
			}else{
				found = true;
			}
		}
		if(found){
			childCount = (current.left?1:0)+(current.right?1:0);
			if(current === this._root){
				switch(childCount){

                    //no children, just erase the root
                    case 0:
                        this._root = null;
                        break;
                    //one child, use one as the root
                    case 1:
                        this._root = (current.right === null ?
                                      current.left : current.right);
                        break;
                    //two children, little work to do
                    case 2:
                    	//开始找，首先我们默认第一个候选人是根节点的左节点
                        replacement = this._root.left;
                        //开始找left subtree的最右边节点
                        while(replacement.right !== null){
                        	replacementParent = replacement;
                        	replacement = replacement.right;
                        }
                        //如果找到最右边的节点，并且不是跟节点的第一个left node
                        if(replacementParent !== null){
                        	//如果我们找到的元素有两种情况，因为我们找的是最右边的node,一个就是leaf node or left node,
                        	replacementParent.right = replacement.left;
                			replacement.left = this._root.left;
                			replacement.right = this._root.right;
                			
                        }else{
                        	//我们的跟节点第一个node就是我们最右边的node
                        	replacement.right = this._root.right;
                        }
                        this._root = replacement;
                }   
			}else{
				switch(childCount){
					case 0:
						//判断是left child or right child
						if(current.value < parent.value){
							parent.left = null;
						}else{
							parent.right = null;
						}
						break;
					case 1:
						if(current.value < parent.value){
							parent.right = current.left ===null ? current.left : current.right;
						}else{
							parent.left = current.left ===null ? current.left : current.right;
						}
						break;
					case 2:
						replacement = current.left;
						replacementParent = current;
						while(replacement.right !== null){
							replacementParent = replacement;
							replacement = replacement.right;
						}
						replacementParent = replacement.left;
						replacement.right = current.right;
						replacement.left = current.left;
						//看看我们要删除的节点是我们的父节点的那个位置
						if(current.value < parent.value){
							parent.left = replacement;
						}else{
							parent.right = replacement;
						}
				}
			}
			
		}
	},
	size: function(){
		var length = 0;
		this.traverse(function(){
			length++;
		});
		return length;
	},
	toString: function(){
		return this.toArray().toString();
	},
	toArray: function(){
		var result = [];
		this.traverse(function(node){
			result.push(node.value);
		});
		return result;
	}
	
})